/*
 * IdentityHashSet.java
 *
 * Created on June 1, 2004, 3:19 AM
 *
 * Copyright 2008 the Desert Labs Project (http://desertlabs.us)
 *
 * Licensed under the Apache License, Version 2.0 (the "License");
 * you may not use this file except in compliance with the License.
 * You may obtain a copy of the License at
 *
 *     http://www.apache.org/licenses/LICENSE-2.0
 *
 * Unless required by applicable law or agreed to in writing, software
 * distributed under the License is distributed on an "AS IS" BASIS,
 * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
 * See the License for the specific language governing permissions and
 * limitations under the License.
 */

package us.desertlabs.collections;

import java.util.AbstractSet;
import java.util.Collection;
import java.util.HashSet;
import java.util.IdentityHashMap;
import java.util.Iterator;
import java.util.Map;


/**
 * This class implements the <CODE>Set</CODE> interface, backed by an <CODE>IdentityHashMap</CODE>
 * instance. Therefore, it uses {@link System#identityHashCode(Object)} instead
 * of {@link Object#equals(Object)} for element comparison during all
 * operations.
 * <P>
 * <B>Similar to <CODE>IdentityHashMap</CODE>, it intentionally violates
 * <CODE>Set</CODE>'s general contract, which mandates the use of the <CODE>equals</CODE>
 * method when comparing objects</B>.
 * <P>
 * It permits <CODE>null</CODE> to be added as an element.
 * <P>
 * <B>Note that this implementation is not synchronized.</B> Multi-threaded
 * access to an instance of this class should be synchronized using the approach
 * described in {@link HashSet}.
 *
 * @param <E> the datatype of the elements
 * @see IdentityHashMap
 * @author Brian Franklin
 */
public class IdentityHashSet<E> extends AbstractSet<E> {

    /** This object is used as a value in the backing <CODE>Map</CODE> */
    final private static Object PRESENT = new Object();

    /**
     * The backing <CODE>IdentityHashMap</CODE> that actually holds the
     * elements of the <CODE>Set</CODE>
     */
    final private Map<E, Object> map;

    /**
     * Creates a new, empty set; the backing <CODE>IdentityHashMap</CODE>
     * instance has the default expected maximum size.
     */
    public IdentityHashSet() {
        map = new IdentityHashMap<E, Object>();
    }

    /**
     * Creates a new set containing the elements in the specified collection.
     * The backing <CODE>IdentityHashMap</CODE> instance is constructed with
     * an expected maximum size equal to the size of the collection.
     *
     * @param c the collection whose elements are to be placed in this set
     */
    public IdentityHashSet(final Collection<E> c) {
        this(c.size());
        addAll(c);
    }

    /**
     * Creates a new, empty set; the backing <CODE>IdentityHashMap</CODE>
     * instance has the specified expected maximum size.
     *
     * @param expectedMaxSize the expected maximum size of the set
     */
    public IdentityHashSet(final int expectedMaxSize) {
        map = new IdentityHashMap<E, Object>(expectedMaxSize);
    }

    /**
     * Adds the specified element to this <CODE>Set</CODE> if it is not
     * already present. The value <CODE>null</CODE> is permitted as an
     * element.
     *
     * @param o the element to add
     * @return <CODE>true</CODE> if the element was added to the <CODE>Set</CODE>;
     *         <CODE>false</CODE> if the element was already present
     */
    @Override
    public boolean add(final E o) {
        if (!map.containsKey(o)) {
            map.put(o, PRESENT);
            return true;
        }
        return false;
    }

    /**
     * Removes all of the elements from this <CODE>Set</CODE>.
     */
    @Override
    public void clear() {
        map.clear();
    }

    /**
     * Returns <CODE>true</CODE> if this <CODE>Set</CODE> contains the
     * specified element.
     *
     * @return <CODE>true</CODE> if this <CODE>Set</CODE> contains the
     *         specified element
     */
    @Override
    public boolean contains(final Object o) {
        return map.containsKey(o);
    }

    /**
     * Compares the specified object with this <CODE>Set</CODE> for equality.
     * Returns the value of the backing <CODE>IdentityHashMap</CODE>'s <CODE>equals</CODE>
     * method.
     * <P>
     * <B>Because of the reference-equality-based semantics of this <CODE>Set</CODE>,
     * it is possible that the symmetry and transitivity requirement of the
     * {@link Object#equals(Object)} contract may be violated if this <CODE>Set</CODE>
     * is compared to a normal <CODE>Set</CODE>. However, the <CODE>Object.equals</CODE>
     * contract is guaranteed to hold among <CODE>IdentityHashSet</CODE>
     * instances.</B>
     *
     * @param o object to be compared for equality with this <CODE>Set</CODE>
     * @return <CODE>true</CODE> if the specified object is equal to this
     *         <CODE>Set</CODE>
     * @see IdentityHashMap#equals(Object)
     */
    @Override
    public boolean equals(final Object o) {
        if( o instanceof IdentityHashSet ) {
            return map.equals(o);
        }
        else {
            throw new IllegalArgumentException("Parameter must be an instance of IdentityHashSet");
        }
    }

    /**
     * Returns the hash code value for this <CODE>Set</CODE>. The hash code
     * value is the hash code value returned from the backing <CODE>IdentityHashMap</CODE>'s
     * key set.
     * <P>
     * <B>Owing to the reference-equality-based semantics of this set, it is
     * possible that the contractual requirement of {@link Object#hashCode()}
     * that ensures <CODE>t1.equals(t2)</CODE> implies <CODE>t1.hashCode()==t2.hashCode()</CODE>
     * will be violated if one of the two objects being compared is an <CODE>IdentityHashSet</CODE>
     * instance and the other is a normal <CODE>Set</CODE>. If both are
     * <CODE>IdentityHashSet</CODE>s, then the contract holds.</B>
     *
     * @return the hash code value for this <CODE>Set</CODE>
     * @see IdentityHashMap#keySet()
     */
    @Override
    public int hashCode() {
        return map.keySet().hashCode();
    }

    /**
     * Returns an iterator over the elements in this <CODE>Set</CODE>. This
     * is the iterator returned from the backing <CODE>IdentityHashMap</CODE>'s
     * key set.
     *
     * @return an iterator over the elements in this <CODE>Set</CODE>
     * @see IdentityHashMap
     * @see IdentityHashMap#keySet()
     */
    @Override
    public Iterator<E> iterator() {
        return map.keySet().iterator();
    }

    /**
     * Removes the specified element from this <CODE>Set</CODE> if it is
     * present.
     *
     * @param o the element to be removed
     * @return <CODE>true</CODE> if the <CODE>Set</CODE> contained the
     *         specified element
     */
    @Override
    public boolean remove(final Object o) {
        return map.remove(o) == PRESENT;
    }

    /**
     * Returns the number of elements in this <CODE>Set</CODE>.
     *
     * @return the number of elements in this <CODE>Set</CODE>
     */
    @Override
    public int size() {
        return map.size();
    }

}
